#include "algorithm"
#include <iostream>
#include <queue>
using namespace std;

#define debug(x) cout << #x <<  " " << x <<  endl;

typedef int Cap;
typedef int Cost;
#define RN 200000

typedef long long ll;
// typedef char C;
// typedef long long L;

class MCMF{
private:
    MCMF();
    MCMF operator=(const MCMF&);
    MCMF(const  MCMF&);
    const static int MAXN = 1000000;const static int N = 1000000;
    int siteNum, clientNum, n, SOURCE_POINT, TARGET_POINT;
    
    // #define SWAP(T, a, b) { T t = a; a = b; b = t; }

// Pools

struct E{ll nxt, to,cap,cost;};


E edge[RN * 2];
ll ncnt = 1;

#define nnode(x) edge[x]
#define ncap(x)  nnode(x).cap
#define ncost(x) nnode(x).cost
ll head[RN], fa[RN], fe[RN], pi[RN], mark[RN], cyc[RN];
ll ti;
inline void _addEdge(ll u, ll v, ll f, ll c)
{
    nnode(++ncnt) = E{head[u], v, f, c };
    head[u] = ncnt;
    nnode(++ncnt) = E{head[v], u, 0, -c };
    head[v] = ncnt;
}

void initTree(ll x){
    mark[x] = 1;
    for (ll i = head[x]; i; i = edge[i].nxt){
        ll v = edge[i].to;
        if (!mark[v] && ncap(i)){
            fa[v] = x, fe[v] = i;
            initTree(v);
        }
    }
}

ll phi(ll x){
    if (mark[x] == ti) return pi[x];
    return mark[x] = ti, pi[x] = phi(fa[x]) - ncost(fe[x]);
}

void pushFlow(ll e, ll *cost){
	ll pen = edge[e^1].to, lca = edge[e].to;
	ti++;
	while (pen)              mark[pen] = ti, pen = fa[pen];
	while (mark[lca] != ti) mark[lca] = ti, lca = fa[lca];
	
	ll e2 = 0, f = ncap(e), path = 2, clen = 0;
	for (ll i = edge[e^1].to; i != lca; i = fa[i]){
		cyc[++clen] = fe[i];
		if (ncap(fe[i]) < f) f = ncap(fe[e2 = i] ^ (path = 0));
	}
	for (ll i = edge[e].to; i != lca; i = fa[i]){
		cyc[++clen] = fe[i] ^ 1;
		if (ncap(fe[i] ^ 1) <= f) f = ncap(fe[e2 = i] ^ (path = 1));
	}
	cyc[++clen] = e;
	
	for (ll i = 1; i <= clen; i++){
		ncap(cyc[i]) -= f, ncap(cyc[i] ^ 1) += f;
		*cost += 1ll * ncost(cyc[i]) * f;
	}
	if (path == 2) return;
	
	ll laste = e ^ path, last = edge[laste].to, cur = edge[laste^1].to;
	while (last != e2){
		mark[cur]--;
		laste ^= 1;
		swap(laste, fe[cur]);
		swap(last, fa[cur]);
		swap(last, cur);
	}
}

ll simplex(ll st, ll ed, ll *cost)
{
	ll lhead = head[st], lhead2 = head[ed];
	_addEdge(ed, st, 0x7fffffffffll, -0x3f3f3f3);
	initTree(ed);
	mark[ed] = ti = 2, fa[ed] = *cost = 0;
	for (ll i = 2, pre = ncnt; i != pre; i = i == ncnt ? 2 : i + 1)
	{
		if (ncap(i) && ncost(i) < phi(edge[i^1].to) - phi(edge[i].to))
			pushFlow(pre = i, cost);
	}
	head[st] = lhead, head[ed] = lhead2, ncnt -= 2;
	return ncap(ncnt + 2);
}

public:
    void clear();
    MCMF(int siteNum, int clientNum);
    void addEdge(int _siteID, int _clientID, int _cap, ll _cost);
    void addEdgeFromSource(int _siteID, int _cap, ll _cost);
    void addEdgeToTarget(int _clientID, int _cap, ll _cost);
    void mcmf(int &_flow, ll &_cost);
    void getSponsor(int clientID, std::vector<std::pair<int,int>>& receptor);
};